\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  给定一张有 \(n\) 个顶点的无向带权图，有 \(m\) 条带权边
\item
  求一种匹配的方案，使得最终匹配边的边权之和最大
\item
  \(ma\) 表示最大匹配权
\item
  \(link[i]\) 表示点 \(i\) 与点 \(link[i]\) 匹配 (\(link[i] = 0\)
  的点没有被匹配)
\item
  复杂度 \(O(n^3)\)
\end{itemize}

\begin{lstlisting}
const int N = 1e3 + 10; 
// N 要开 1.5 倍以上 
// 答案记得开 long long 
struct Edge
{
	int u, v, w;
	Edge() {}
	Edge(int a , int b , int c)
	{
		u = a , v = b , w = c;
	}
} g[N][N];
int n, m, n_x, lab[N], link[N], slack[N], st[N], pa[N], from[N][N], S[N], vis[N];
vector<int> flower[N];
deque<int> q;
int dist(Edge e)
{
	return lab[e.u] + lab[e.v] - e.w * 2;
}
void update_slack(int u, int x)
{
	if (!slack[x] || dist(g[u][x]) < dist(g[slack[x]][x]))
		slack[x] = u;
}
void set_slack(int n, int x)
{
	slack[x] = 0;
	rep(u , 1 , n) if(g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) update_slack(u, x);
}
void q_push(int n, int x)
{
	if (x <= n) return q.push_back(x);
	for (int i = 0; i < flower[x].size(); i ++) q_push(n, flower[x][i]);
}
void set_st(int n, int x, int b)
{
	st[x] = b;
	if(x <= n) return;
	for (int i = 0; i < flower[x].size(); i ++) set_st(n, flower[x][i], b);
}
int get_pr(int b, int xr)
{
	int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin();
	if (pr % 2 == 1) //检查它在前一层是奇点还是偶点 
	{
		reverse(flower[b].begin() + 1, flower[b].end());
		return (int)flower[b].size() - pr;
	}
	else return pr;
}
void set_match(int u, int v)
{
	link[u] = g[u][v].v;
	if (u <= n)
		return;
	Edge e = g[u][v];
	int xr = from[u][e.u], pr = get_pr(u, xr);
	for (int i = 0; i < pr; ++i)
		set_match(flower[u][i], flower[u][i ^ 1]);
	set_match(xr, v);
	rotate(flower[u].begin(), flower[u].begin() + pr, flower[u].end());
}
void Aug(int n, int u, int v)
{
	int xnv = st[link[u]];
	set_match(u, v);
	if (!xnv)
		return;
	set_match(xnv, st[pa[xnv]]);
	Aug(n, st[pa[xnv]], xnv);
}
int get_lca(int u, int v)
{
	static int t = 0;
	for (++t; u || v; swap(u, v))
	{
		if (u == 0) continue;
		if (vis[u] == t) return u;
		vis[u] = t; //这种方法可以不用清空 v 阵列 
		u = st[link[u]];
		if (u) u = st[pa[u]];
	}
	return 0;
}
void add_blossom(int n, int u, int LCA, int v)
{
	int b = n + 1;
	while (b <= n_x && st[b]) b++;
	n_x = max(n_x, b);
	lab[b] = S[b] = 0;
	link[b] = link[LCA];
	flower[b].clear();
	flower[b].pb(LCA);
	for (int x = u, y; x != LCA; x = st[pa[y]])
	{
		flower[b].pb(x);
		y = st[link[x]];
		flower[b].pb(y);
		q_push(n, y);
	}
	reverse(flower[b].begin() + 1, flower[b].end());
	for (int x = v, y; x != LCA; x = st[pa[y]])
	{
		flower[b].pb(x);
		y = st[link[x]];
		flower[b].pb(y);
		q_push(n, y);
	}
	set_st(n, b, b);
	rep(i , 1 , n_x) g[b][i].w = g[i][b].w = 0;
	rep(i , 1 , n) from[b][i] = 0;
	for (auto xs : flower[b])
	{
		rep(x , 1 , n_x) if (g[b][x].w == 0 || dist(g[xs][x]) < dist(g[b][x]))
		{
			g[b][x] = g[xs][x];
			g[x][b] = g[x][xs];
		}
		rep(x , 1 , n)
		if (from[xs][x])
			from[b][x] = xs;
	}
	set_slack(n, b);
}
void expand_blossom(int n, int b)
{
	for(auto i : flower[b]) set_st(n, i, i);
	int xr = from[b][g[b][pa[b]].u];
	int pr = get_pr(b, xr);
	for (int i = 0; i < pr; i += 2)
	{
		int xs = flower[b][i];
		int xns = flower[b][i + 1];
		pa[xs] = xns;
		S[xs] = 1;
		S[xns] = 0;
		slack[xs] = 0;
		set_slack(n, xns);
		q_push(n, xns);
	}
	S[xr] = 1;
	pa[xr] = pa[b];
	for (int i = pr + 1; i < flower[b].size() ; i ++)
	{
		int xs = flower[b][i];
		S[xs] = -1;
		set_slack(n, xs);
	}
	st[b] = 0;
}
bool on_found_Edge(int n, const Edge &e)
{
	int u = st[e.u], v = st[e.v];
	if (S[v] == -1)
	{
		pa[v] = e.u;
		S[v] = 1;
		int nu = st[link[v]];
		slack[v] = slack[nu] = 0;
		S[nu] = 0;
		q_push(n, nu);
	}
	else if (S[v] == 0)
	{
		int LCA = get_lca(u, v);
		if(!LCA)
		{
			Aug(n, u, v) , Aug(n, v, u);
			return true;
		}
		else add_blossom(n, u, LCA, v);
	}
	return false;
}
bool matching(int n)
{
	rep(i , 0 , n_x + 1) S[i] = -1 , slack[i] = 0;
	q.clear();
	rep(i , 1 , n_x) if(st[i] == i && !link[i])
	{
		S[i] = pa[i] = 0;
		q_push(n, i);
	}
	if (q.empty()) return false;
	for( ; ; )
	{
		while (!q.empty())
		{
			int u = q.front();
			q.pop_front();
			if (S[st[u]] == 1)
				continue;
			for (int v = 1; v <= n; v++)
				if (g[u][v].w > 0 && st[u] != st[v])
				{
					if (dist(g[u][v]) == 0 && on_found_Edge(n, g[u][v]))
						return true;
					else if (dist(g[u][v]) != 0)
						update_slack(u, st[v]);
				}
		}
		int d = 0x3f3f3f3f;
		rep(b , n + 1 , n_x) if(st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
		rep(x , 1 , n_x) if(st[x] == x && slack[x])
		{
			if(S[x] == -1) d = min(d, dist(g[slack[x]][x]));
			else if(S[x] == 0) d = min(d, dist(g[slack[x]][x]) / 2);
		}
		rep(u , 1 , n)
		{
			if(S[st[u]] == 0)
			{
				if(lab[u] <= d) return false;
				lab[u] -= d;
			}
			else if(S[st[u]] == 1) lab[u] += d;
		}
		rep(b , n + 1 , n_x) if(st[b] == b)
		{
			if(S[st[b]] == 0) lab[b] += d * 2;
			else if(S[st[b]] == 1) lab[b] -= d * 2;
		}
		q.clear();
		rep(x , 1 , n_x)
		{
			if(st[x] == x && slack[x] && st[slack[x]] != x && !dist(g[slack[x]][x]))
				if(on_found_Edge(n, g[slack[x]][x]))
					return true;
		}
		rep(b , n + 1 , n_x)
		{
			if(st[b] == b && S[b] == 1 && lab[b] == 0)
				expand_blossom(n, b);
		}
	}
	return 0;
}
pair<long long, int> solve(int n)
{
	long long sum = 0;
	int cnt = 0, ma = 0;
	rep(i , 1 , n) rep(j , 1 , n) ma = max(ma, g[i][j].w);
	rep(i , 1 , n) lab[i] = ma;
	while(matching(n)) cnt ++;
	rep(i , 1 , n)
	if (link[i] && link[i] < i)
		sum += (long long)g[i][link[i]].w;
	return make_pair(sum, cnt);
}
void init(int n)
{
	n_x = n;
	rep(i, 0, n + 1)
	{
		rep(j, 0, n + 1)
		{
			g[i][j] = Edge {i, j, 0};
			from[i][j] = 0;
		}
		from[i][i] = i;
		link[i] = 0;
		st[i] = i;
		flower[i].clear();
	}
}
signed main()
{
	cin >> n >> m;
	init(n);
	rep(i, 1, m)
	{
		int u, v, w;
		cin >> u >> v >> w;
		w = max(w, g[u][v].w);
		g[u][v].w = g[v][u].w = w;
	}
	long long ma = solve(n).first;
	cout << ma << '\n';
	rep(i, 1, n) cout << link[i] << " \n"[i == n];
	return 0;
}
\end{lstlisting}

\end{document}
